1. Field of the Invention
This invention generally relates to communication systems. More specifically, the present invention relates to a medium access control (MAC) protocol for use in a multi-channel communication system based on, for example, Code Division Multiple Access (CDMA), Wavelength Division Multiple Access (WDMA), Frequencies Division Multiple Access (FDMA) or other multiple-channel systems.
2. Description of Related Art
In a typical wireless communication system, messages are transmitted asynchronously via data packets between a base station (BS) and a plurality of mobile stations (MS). Each of the data packets includes an information portion containing a coded message and a header description portion containing codes indicating the terminals destined to receive the message. The wireless communication system may be a single-channel system, based on, for example, TDMA in which the data packets are transmitted serially and successively in the same channel in the time domain (i.e., they are transmitted in different time-slots in the same channel), or a multi-channel system, such as CDMA, FDMA, or WDMA, in which the data packets are transmitted either serially in the same channel or concurrently in different channels.
FIG. 1 illustrates a conventional single-channel wireless communication system. The system has an uplink channel 12 and a downlink channel 14 which carry data packets between mobile stations 161-163 and base station 18.
FIG. 2 shows a conventional multi-channel wireless communication system 20 having a plurality of uplink channels 221-223 and downlink channels 241-243. Uplink channels 221-223 are used to transmit data packets from mobile stations 261-263 to a base station 28. Downlink channels 241-243 transmit data packets form base station 28 to mobile stations 261-263. The systems shown in FIGS. 1 and 2 are contentional systems in which the respective mobile stations share one or more common channels in a manner that can lead to conflicts.
The following references provide background information relating to wireless communication systems and are hereby incorporated by reference in their entireties:
(1) D. Bertsekas, and R. Gallager, xe2x80x9cData Networksxe2x80x9d, 2nd edition, Prentice-Hall Inc.
(2) A. Tanenbaum, xe2x80x9cComputer Networksxe2x80x9d, 3rd edition, Prentice-Hall Inc., 1996;
(3) ETSI, xe2x80x9cRadio Equipment and Systems (RES); High Performance Radio Local Area Network (HIPERLAN); Functional Specification,xe2x80x9d Version 1.1 25/01/1995;
(4) G. A. Halls, xe2x80x9cHIPERLAN: The High Performance Radio Local Area Network Standard,xe2x80x9d Electronic and Communication Engineering Journal, pp. 289-296;
(5) Raychaudhuri, . . . et al., xe2x80x9cMultiservices Medium Access Control Protocal for Wireless ATM Systemxe2x80x9d, U.S. Pat. No. 5,638,371, June 1997;
(6) D. Raychaudhuri, and N. D. Wilson, xe2x80x9cATM-Based Transport Architecture for Multiservices Wireless Personal Communication Networks,xe2x80x9d IEEE Journal on Selected Area in Communications, Vol. 12, No. 8, October 1994, pp. 1401-1414;
(7) W. Yue, xe2x80x9cThe Effect of Capture on Performance of Multichannel Slotted ALOHA Systemsxe2x80x9d, IEEE Transactions on Communications, Vol. 39, No. 6, Jun. 1991, pp. 818-822;
(8) Z. Liu, and M. El Zarki, xe2x80x9cPerformance Analysis of DS-CDMA with Slotted ALOHA Random Access for Packet PCNsxe2x80x9d, ACM/Baltzer Wireless Networks, Vol. 1, No. 1, February 1995, pp. 1-16;
(9) Chen et al., xe2x80x9cMethod of Controlling the Operation of a Packet Switched CDMA Telecommunication Networkxe2x80x9d, U.S. Pat. No. 5,394,391, February 1995;
(10) Umeda et al., xe2x80x9cRandom Access Communication Method by CDMA and Mobile Station Equipment Using the Samexe2x80x9d, U.S. Pat. No. 5,581,547, December 1996;
(11) Raychaudhuri et al., xe2x80x9cStabilization of Random Access Packet CDMA Networksxe2x80x9d, U.S. Pat. No. 4,841,527, June 1989;
(12) I. M. I. Habbab, M. Kavehrad, and C. W. Sundberg, Protocols for Very High-speed Optical Fiber Local Area Networks Using a Passive Star Topologyxe2x80x9d, IEEE Journal of Lightwave Technology, Vol. LT-5, No. 12, December 1987, pp. 1782-1793;
(13) ETSI SMG2, xe2x80x9cConcept group Alpha-Wideband Direct-Sequence CDMA, EVALUATION DOCUMENT (DRAFT 1.0), Part 1: System Description and Performance Evaluationxe2x80x9d, UMTS Terrestrial Radio Access (UTRA), draft document, October 1997;
(14) Quick, Jr., xe2x80x9cRandom Access Communications Channel for Data Servicesxe2x80x9d, U.S. Pat. No. 5,673,259, September 1997;
(15) Argyroudis et. al., xe2x80x9cWireless Remote Telemetry Systemxe2x80x9d, U.S. Pat. No. 5,748,04, May 1998;
(16) TIA TR45.5, xe2x80x9cThe CDMA2000 ITU-R RTT Candidate Submissionxe2x80x9d, June 1998.
(17) ETSI standard GSM 03.64, version 5.2.0, xe2x80x9cDigital Cellular telecommunications System (Phase 2+): General Packet Radio Services (GPRS); Overall description of the GPRS radio interface, stage 2xe2x80x9d, January 1998;
(18) ETSI draft standard GSM 04.60, version 2.00, xe2x80x9cDigital Cellular Telecommunications System (Phase 2+): General Packet Radio Services (GPRS); Mobile Station (MS)-Base Station System (BSS) Interface; Radio Link Control/Medium access Control Protocolxe2x80x9d, March 1998;
(19) A Polydoros, and J. Silvester, xe2x80x9cSlotted Random Access Spread-Spectrum Networks: An Analytical Frameworkxe2x80x9d, IEEE Journal on Selected Areas in Communication, Vol. SAC-5, No. 6 Jul. 1987, pp. 989-1002;
(20) D. Makrakis, and K. M. S. Murthy, xe2x80x9cSpread Slotted ALOHA Techniques for Mobile and Personal Satellite Communication Systemsxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 10, No. 6, Aug. 1992, pp. 985-1002; and
(21) K Toshimitsu, T. Yamazato, M. Katayama, and A. Ogawa, xe2x80x9cA Novel Spread Slotted ALOHA System with Channel Load Sensing Protocolxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 12, No. 4, May 1994, pp. 665-672.
Channel conflicts in single-channel wireless communication systems are generally resolved through the implementation of protocols such as Slotted ALOHA, Carrier Sense Multiple Access (CSMA), Attempt and Defer, and Reservation, which are disclosed, e.g., in references [1] and [2]. In the Slotted ALOHA protocol, for example, all mobile stations wanting to send a data block are assumed to be synchronized in time-slots over the shared uplink channel. Any mobile station may choose, in a random manner, a time-slot to send its data block. If two or more mobile stations attempt to access the same time-slot, a collision occurs and all mobile stations in this attempt will back off and wait for a random number of time-slots before they make another attempt. The throughput is limited, i.e., less than 0.368.
In the CSMA scheme, the mobile station desiring to send a data block will attempt to sense an open channel prior to sending its data block. If a busy signal is detected, each mobile station with an attempt will wait until the channel is open. This is sometimes called xe2x80x9cListen Before Send.xe2x80x9d The CSMA systems handles the occurrence of an access collision in the same way as the Slotted ALOHA protocol. However, the CSMA has improved performance relative to the Slotted ALOHA protocol, achieving a throughput of between 0.5 and 0.7.
In the Attempt and Defer protocol, as shown in FIG. 3, the data packet access process includes two phases, i.e., a contention resolution phase 30 and a data transmission phase 32. In the contention resolution phase, all mobile stations 341-344 with attempts 361-364 become involved in a resolution process in which the occurrence of a collision is resolved by determining a successful mobile station that is permitted to transmit a data packet 38 in the data transmission phase 32. Variances in the Attempt and Defer protocol, including Multi-Level Multi-Access or Binary Countdown as disclosed in reference [2] and the European wireless local network standard HiPERLAN as disclosed in references [3] and [4], also use bit sequences to compete for the access right, which results in at most one mobile station that successfully sends a data packet during the data transmission phase.
In the Reservation protocol illustrated in FIG. 4, there are three phases, i.e., request phase 40, reservation phase 41, and data transmission phase 42. In the request phase 40, one or more mobile stations can send request messages on an uplink channel 43 via one of the control time-slots 44. However, because the request messages are sent on a contention basis, they may collide with one another (note that the Slotted ALOHA protocol may be incorporated, for instance, to resolve this collision problem). Upon receiving the request messages from the mobile stations, the base station makes an assignment 45 in the reservation phase 41 and communicated via a downlink channel 46 to determine which of the corresponding mobile stations is permitted to send a data packet 47 during the transmission phase 42. A MAC access frame 48 includes the request phase 40 and the data transmission phase 42. Typical protocols of this category are Dynamic TDMA used in the wireless asynchronous transmission mode (ATM) system as disclosed in references [5] and [6].
Channel conflicts in a multi-channel wireless communication system, on the other hand, can be resolved through conventional protocols such as the Distributed Method and the Centralized Method. The Distributed Method, which is usually based on the ALOHA protocol, is often called a multi-channel ALOHA protocol. The multi-channel ALOHA protocol can be further categorized into two types, i.e., receiver-oriented and transmitter-oriented. Generally, in a multi-channel system with N channels, each mobile station is assumed to have N different receivers (transmitters) and one unique transmitter (receiver) for transmitter-oriented operation. In the transmitter-oriented method, each mobile station has the capability of receiving k data packets concurrently on all of the N channels. If there are M mobile stations in the system, let MSi represent the ith mobile station and ti represent the transmitter that is able to send packets on one unique channel cj from the N channels, where i=1 . . . M,j=1 . . . N . . . Letf(ti)=cj mean that MSi is equipped with the transmitter ti on the channel cj. If f(ti)=cj and MSi has a transmission attempt, MSi sends a data packet on channel cj and then waits for the acknowledgment from the receiver. If no acknowledgment or negative acknowledgment is received, MSi waits for a random time and tries again. A negative acknowledgment occurs when the following condition takes place: (1) more than one transmitters send data packets on the same channel cj, (2) more than k packets are sent to one receiver, and (3) a noisy communication link exists. The condition for a receiver-oriented protocol is very similar to the transmitter-oriented protocol discussed above.
The performance of the above-described distributed multi-channel system has been studied, e.g., in references [7] and [8]. It was shown that the normalized throughput is only between 0.25 and 0.5 when k is between 1 and 3. The performance of the multi-channel ALOHA system on a CDMA network was further studied in reference [8]. A drawback of the multi-channel ALOHA technique is that all attempts will be transmitted regardless of their success or failure. That is, all mobile stations wishing to send data packets will be permitted to send, and the colliding data packets will create a certain level of noise with regard to the successful data packets. This creates serious problems on CDMA systems since unnecessary signals become an interference source creating a high noise level in the communication link. For example, the maximal throughput of the Multi-channel ALOHA protocol in a CDMA network is around 0.3, which means that the failed packets may produce a noise level up to 0.7. This noise seriously degrades the performance of the CDMA network, and may interfere with the successful packets and result in additional errors. Several U.S. patents as disclosed in references [9], [10], and [11] relate to this category.
Other schemes use, e.g., a dedicated control channel to coordinate the transmission of data packets. For instance, a scheme called ALOHA/ALOHA is described in reference [12] and shown in FIG. 5. All mobile stations 50i-50w wishing to send data packets via data channels 52i-52w first send their attempts on a control channel 54. Each attempt includes three information elements, i.e., a source mobile station 55, a target mobile station 56, and a selected data channel w 57. The source mobile station will send a data packet 58 on the selected channel w shortly after the attempt message was sent. In the meantime, all mobile stations 50i-50w listen to the control channel 54. If there is a message indicating that the source mobile station (e.g., MS1) is about to send a data packet to a target mobile station (e.g., MS2), the target mobile station will be directed to receive the data packet on the appropriate channel. This scheme is similar to the random access protocol proposed for the wideband DS-CDMA as disclosed in reference [13].
Another category of techniques is denominated the Centralized Method which is contrasted with the distributed method described above. The Centralized Method protocol is shown in FIG. 6. In FIG. 6, a base station 60 is used to coordinate the whole traffic regarding packet transmission and receiving. In particular, two dedicated control channels, i.e., an access channel 61 and a page channel 62, as disclosed in references [14] and [15], are used. Channels other than the above two control channels are referred to as traffic or data channels 63i-63w. In this method, all communications among mobile stations 641-643 are completed via the base station 60. There are two types of channel directions, i.e., uplink (reverse) and downlink (forward). The uplink channel carries data messages from the mobile stations 641-643 to the base station 60, and the downlink channel carries a grant message 65 from the based station 60 to the mobile stations 641-643. Any mobile station wishing to send a data packet 66 can send a request message 67 to the base station via the access channel 61. The access channel 61 is subjected to contention since two or more mobile stations may raise their requests simultaneously. If a request message is successfully received by the base station, the base station will send a grant message 65 to the source mobile station via the page channel 62. The grant message 65 indicates that the source mobile station was granted permission to send a data packet on one of the data channels. For example, the grant message 65 may contain information such as the data channel number and time-to-send request.
One drawback of the Centralized Method involves access delay (i.e., the passage of time between submitting a request and receiving a grant), which can be relatively long especially when the number of mobile stations is large. Additionally, the traffic load on the access channel can be relatively high in the Centralized Method, which in turn can further increase the access delay.
The conventional MAC protocol is discussed in, e.g., reference [1]. Conventional MAC protocols such as the multi-channel slotted ALOHA protocol ate typically used in communication systems being considered by the International Telecommunication Union technology, such as the Wideband Direct Sequence (DS)-CDMA technology as disclosed in reference [13] or the CDMA-2000 technology as disclosed in reference [16] to facilitate its random access scheme and resolve contention problems. The Wideband DS-CDMA system is particularly applicable to a third generation mobile system which will provide a higher bit rate, more service categories, and more efficient radio access to the mobile stations, for example, packet-based radio access and variable bit rate transmission. Consideration of inter-operation with other existing mobile systems such as GSM, IS-95 and IS-136 are important issues. Communication systems for use in the third generation mobile systems are the GSM phase 2 plus General Packet Radio Service (GPRS) disclosed in references [17] and [18] and the multi-code spread slotted ALOHA disclosed in references [9], [19], [20], and [21]. The typical approach usually assumes there are m different CDMA receivers/transmitters, each able to transmit/receive data that are spread by a certain code. A slotted ALOHA scheme is then applied such that each user first randomly selects a spreading code for transmitting/receiving, then the slotted ALOHA in the time domain is performed afterwards. A disadvantage of this approach is the high complexity of each mobile station. The random access scheme presented in the Wideband DS-CDMA system uses a preamble code and a time-offset before the transmission of each data packet. It minimizes the complexity of mobile stations by requiring that all communications between two mobile stations be via a base station, thus putting most of the complexity on the base station. However, since the basic access scheme is multi-code spread slotted ALOHA, a failed random access attempt will still produce unnecessary interference and a great amount of code resources are reserved for channel access, resulting in low channel efficiency.
The original random access scheme in the Wideband DS-CDMA described in reference [1]is shown in FIG. 8. Each packet 821-824 (called a Random-Access Burst) from the mobile stations 841-844 is transmitted within a frame period 86 of 10 milliseconds (ms). Each of the packets 821-824 has two parts, i.e., a preamble part 82A of length 16*256 chips (lms) and a data part 82B of variable length. The preamble code in the preamble part 82A consists of 16 symbols spread by an Orthogonal Gold code of length 256 chips. Up to 16 simultaneous transmissions of the packets 821-824 can be successfully received in each cell. One of the 16 preamble codes is randomly chosen at each random access attempt.
As shown in FIG. 8, each 10 millisecond frame 86 is further divided into five time-offsets of 2 millisecond periods 88. Each of the data packets 821-824 can only be transmitted in a j*2 mobile station time-offset (j=0,1,2,3, or 4) relative to the 10 mobile station frame boundary. The data part 82B of the packet will be spread and modulated using another scrambling code that will be chosen based on the randomly chosen preamble code and the randomly chosen time-offset. That is, one of 80 orthogonal scrambling codes will be selected for each random access attempt. Since each preamble code is one millisecond long, it guarantees that two simultaneous random access attempts that use different preamble codes and/or different time-offsets will not collide during the data part of the packet. With this scheme, a base station may receive up to 80 random access attempts within one 10 millisecond frame.
In this scheme, let pi denote the ith preamble code i=0 . . . 15, tj denote the jth time-offset (j=0 . . . 4) and sk denote the kth scrambling code for data part (k=0 . . . 79). Also, let P represent the set of all preamble codes, T represent the set of all time-offsets, and xcexa8 represent the set of all scrambling codes. Their relation is summarized as follows:
Definition 1: A function of f: PxTxe2x86x92Y is a 1-to-1 mapping function where
∀pixcex5P, ∀tjxcex5T, ∀skxcex5xcexa8, and f(pi,tj)=si+16jxe2x80x83xe2x80x83(1) 
Although mobile stations may select different time-offsets as their stating point of random access attempts, all data parts can be as long as 10 ms. As a result, random access attempts on different time-offsets will use different scrambling codes. For example, as shown in FIG. 9, the data packets 921-924 each consisting of, e.g., a preamble part 92A and a data part 92B are transmitted from the mobile stations 941-944 during the frame period 961 of 10 mobile station (i.e., five subframes 98 of 2 milliseconds each) or the subsequent frame period 962 of 10 milliseconds. The data part 92B having a length 99 of 10 milliseconds may be extended to the beginning of the same time-offset of the next frame 962.
Additionally, assuming that there are n mobile stations, each having a data packet arrival probability of xcex (in every 10 millisecond frame), the probability that a mobile station successfully transmits a data packet in a frame is                               λ          ⁢                                    ∑                              z                =                1                            n                        ⁢                          xe2x80x83                        ⁢                                                            (                                      1                    -                    λ                                    )                                                  n                  -                  z                                            ·                              λ                                  z                  -                  1                                            ·                                                (                                      1                    -                                          1                                                                        "LeftBracketingBar"                          P                          "RightBracketingBar"                                                ·                                                  "LeftBracketingBar"                          T                          "RightBracketingBar"                                                                                                      )                                                  z                  -                  1                                            ·                              (                                                                                                    n                        -                        1                                                                                                                                                n                        -                        z                                                                                            )                                                    =                                            λ              ⁡                              (                                  1                  -                  λ                  +                  λ                                )                                      ⁢                                          (                                  1                  -                                      1                                                                  "LeftBracketingBar"                        P                        "RightBracketingBar"                                            ·                                              "LeftBracketingBar"                        T                        "RightBracketingBar"                                                                                            )                                            n                -                1                                              =                                    λ              ⁡                              (                                  1                  -                                      λ                                                                  "LeftBracketingBar"                        P                        "RightBracketingBar"                                            ·                                              "LeftBracketingBar"                        T                        "RightBracketingBar"                                                                                            )                                                    n              -              1                                                          (        2        )            
Since a random access attempt may occasionally fail, it will be backlogged temporarily and will need a retransmission in one of the following frames. This results in an effect that the traffic load offered by each mobile station is actually larger than the packet arrival rate xcex. Let xcexa denote the offered load consisting of packet arrival rate xcex and backlogged retransmission attempt. The successful probability in Equation (2) should be modified to be                     =                              k            ⁡                          (                              1                -                                  k                                                            "LeftBracketingBar"                      P                      "RightBracketingBar"                                        ·                                          "LeftBracketingBar"                      T                      "RightBracketingBar"                                                                                  )                                            n            -            1                                              (        3        )            
The average system throughput is defined as the number of successful packet transmissions in each frame (packets/frame). Since there are n mobile stations, the system throughput is therefore equal to                     =                              nk            ⁡                          (                              1                -                                  k                                                            "LeftBracketingBar"                      P                      "RightBracketingBar"                                        ·                                          "LeftBracketingBar"                      T                      "RightBracketingBar"                                                                                  )                                            n            -            1                                              (        4        )            
A plot for Expression (4) is shown in FIG. 10 in which |P|=16 and |T|=5 (see reference [13]). The maximum throughput is 29.44 packets/frame out of 80 simultaneous random access attempts. The result (29.44/80=0.368) matches the result for slotted ALOHA in the TDMA system. The difference is that it is now in the form of hybrid TDMA/CDMA. The case for a multi-code spread slotted ALOHA in CDMA system is even worse than slotted ALOHA in TDMA, which has a low throughput and unstable performance. Failed random access attempts will create unnecessary interference over the successful transmissions since all attempts are transmitted in parallel. In CDMA systems, the reduction of interference is as important as the increase of throughput when a MAC protocol is designed. For instance, assuming that there are 30 mobile stations having uplink access attempts, only 11 (0.368*30) of them will be successful and the other 19 attempts will become noise to the successful signals. This is a serious problem in wireless communications.
An additional problem of the WCDMA random access scheme is in its code allocation. There is no flexibility in code assignment. Any mobile station can randomly choose a scrambling code sk (determined by the preamble code and time-offset). The multi-channel wireless system using the WCDMA random access scheme has to reserve a total number of 80 scrambling codes for random access, while achieving only a maximum throughput of 0.368. This creates a seriously inefficient allocation of radio resources.
In view of the foregoing disadvantages with the prior art systems, it is the object of the present invention to provide an improved MAC protocol for use in a multi-channel wireless communication system to reduce communication interference and minimize access delay.
It is another object of the present invention to provide a new MAC protocol which improves the random access method in Wideband DS-CDMA by adding the processes of contention resolution and code assignment into the random access scheme such that allocation of code resources is highly flexibly controlled and unnecessary random access attempts are avoided to obviate interference from failed access attempts.
The present invention achieves the above objects in a multi-channel communication system for wireless data communication comprising a first station, a plurality of second stations, and a medium access control protocol for controlling the operation of the data communications between the first station and the second stations, wherein the communication operation comprises (1) transmitting request packets from the second stations to the first station, each of the request packets including a preamble code and a padding code encoded by a random access scrambling code, (2) transmitting a series of code assignment commands encoded by a channelization code from the first station to the second stations based on the request packets processed by the first station, and transmitting the data packets encoded by data scrambling codes from the second stations to the first station based on the assignment commands. In one embodiment, the system is a WCDMA system wherein the first station is a base station and the second stations are mobile stations.
Other features and advantages of the invention will become apparent upon reference to the following description of the preferred embodiments when read in light of the attached drawings.